#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "algorithm"

using namespace std;


int findKthNumber1(int n, int k) {

    int num = 1;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (i == k - 1)
            return num;

        if (num * 10 <= n) {
            count++;
            num *= 10;
        } else {
            //如果num等于最后一个数
            //或者num=最后一个数
            while (num % 10 == 9 || num == n) {
                num = num / 10;
            }

            num++;//否则数量相加
        }


    }

    return num;
}

int getNodeNumber(int n, long cur) {
    //
    long next = cur + 1;//当前节点右边的节点

    //统计合格的节点数

    long totalNodes = 0;

    // 当当前节点num小于最大节点时候
    while (cur <= n) {
        // 这里是最关键的一步:当n不在cur层时,该层有效节点数目为next - cur(全部都要了)
        // 当n在cur层时,该层有效节点数目为n - cur + 1(要一部分)
        // 统一起来就是取最小值
        //这边实属懵逼。妈蛋改成10也不对不能全A
        totalNodes = totalNodes + min(long(n - cur + 1), long(next - cur));
        // cur与next均向下计算
        cur *= 10;
        next *= 10;

    }


    return totalNodes;

}

//TODO 谁写写傻逼
int findKthNumber(int n, int k) {

    int cur = 1;//记录当前number就是那个树的顺序

    //来记录k 第几个数每次确定一个数就-1
    k--;//因为1 已经确定了
    while (k > 0) {
        //获取以cur开头的所有子树下的所有节点
        int nodes = getNodeNumber(n, cur);

        //说明没在这个子树上 因为这个子树的所有节点都比这个小
        if (nodes <= k) {
            cur++;//说明在右边这边确定了一个
            k -= nodes;

        } else {
            // 若nodes>k的话说明把nodes个节点够分
            // cur往下走
            cur *= 10;
            // 将cur计算进k
            k--;

        }


    }



// 最后cur会停留在第k小的数上
    return (int) cur;

}